This video discusses the problems that programmers face with Array Data Structures and the need of coming up with Linked List as the alternative.
This track of the course covers the topic "Linked List".
In details, this track will cover:
Objective: The objective of this track is to familiarize the learners with Linked List.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
This video discusses the problems that programmers face with Array Data Structures and the need of coming up with Linked List as the alternative.
This video discusses the introductory part of the Linked List Data Structure.
This video talks about implementation of a simple singly linked list with three nodes.
CodeThis video talks about creation of a simple linked list with 3 nodes in Java.
Code:
This video talks about traversal of a linked list from head to last node.
Code:
This video talks of traversal of a linked list from head to last node.
Code:
Implementation of recursive function to print a singly linked list
The video discusses both C++ and Java codes for insert at the beginning of Singly Linked List
Codes:
In this video both C++ and Java codes are discussed to insert a node at the end of linked list
Codes:
This video talks about function to delete first node of linked list.
Codes:
This video talks about deletion of last node of a singly linked list.
Codes:
Approach and implementation of insertion at given position in a singly linked list are discussed
This video talks about finding position of an element in a linked list. This video talks about both iteratative and recursive solutions.
Codes:
This video discusses insertion at the beginning of Doubly Linked List
Codes:
Approach and implementations to insert a node at the beginning of doubly linked list are discussed
Code:
This video discusses reversal of doubly linked list.
This video talks about deleting first node of a given doubly linked list.
Codes:
This video talks about deleting last node of a doubly linked list
Codes:
This video talks about two methods for traversal of a circular linked list in C++.
Codes:
This video talks about two methods of circular linked list traversal in Java.
Codes:
This video talks about two methods.
1) Naive : O(n)
2) Efficient : O(n)
Codes:
This video talks about two methods to insert at the end.
1) Naive : O(n)
2) Efficient : O(1)
Codes:
This video talks about deleting first node of a circular linked list
Codes:
This video talks about deleting kth node of a circular linked list where k is less than or equal to the number of nodes in the list.
Codes:
This video introduces circular doubly linked list. It talks about its advantages and insertion.
Codes:
This video discusses insertion in a sorted linked list. The linked list should remain sorted after insertion.
This is an important interview problem where one needs to find the middle of a linked list of a given linked list.
Codes:
This video discusses the problem on finding the n-th node from the end of a given linked list.
Codes:
This video discusses the problem of reversing a linked list in an iterative manner.
Codes:
This video discusses the problem of reversing a linked list in a recursive manner.
Codes:
In this method a tail recursive solution is discussed to reverse the linked list. This method simply follows the iterative solution.
Codes:
Approach and implementation of a function to remove duplicates from a sorted singly linked list
Two methods are discussed here :
1) Recursive
2) Iterative
Codes:
This video discusses the problem of checking whether a linked list contains any loop or not. We would discuss the four methods involved in detecting loops in a linked list, one more efficient than other.
Codes:
This video discusses the problem of detecting a loop using the method of Floyd cycle detection.
Codes:
This video discusses the problem of detecting and removing a loop from the linked list
Codes:
This is one of the tricky problem asked in an interview where a random address to a node of the linked list is given and the user needs to delete the node of the given address. The address can point to any random node in-between a linked list.
Codes:
Given a singly linked list, the task is to segregate or separate the even and odd nodes of the linked list.
Codes:
Intersection of two linked list new
Codes:
Pairwise swap nodes of linked list
Codes:
Clone a linked list using a random pointer
Codes:
LRU Cache Design Discussion using Naive and Efficient Implementation
Codes:
A O(m+n) time and O(1) auxiliary space solution is discussed.
Codes:
Palindrome Linked List
Codes:
Linked Lists are linear or sequential data structures in which elements are stored at non-contiguous memory locations and are linked to each other using pointers.

id[] = [1000, 1010, 1050, 2000, 2040].And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000). Deletion is also expensive with arrays unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved.
Representation of Linked Lists
A linked list is represented by a pointer to the first node of the linked list. The first node is called the head node of the list. If the linked list is empty, then the value of the head node is NULL.struct NodeIn Java, LinkedList can be represented as a class, and the Node as a separate class. The LinkedList class contains a reference of the Node class type.
{
int data;
struct Node* next;
};
class LinkedList
{
Node head; // head of list
/* Linked list Node*/
class Node
{
int data;
Node next;
// Constructor to create a new node
// Next is by default initialized
// as null
Node(int d) {data = d;}
}
}
// A simple C/C++ program to introduce
// a linked list
#include<bits/stdc++.h>
using namespace std;
// Linked List Node
struct Node
{
int data; // Data
struct Node *next; // Pointer
};
// Program to create a simple linked
// list with 3 nodes
int main()
{
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;
// allocate 3 nodes in the heap
head = new Node;
second = new Node;
third = new Node;
/* Three blocks have been allocated dynamically.
We have pointers to these three blocks as first,
second and third
head second third
| | |
| | |
+---+-----+ +----+----+ +----+----+
| # | # | | # | # | | # | # |
+---+-----+ +----+----+ +----+----+
# represents any random value.
Data is random because we haven’t assigned
anything yet */
head->data = 1; //assign data in first node
// Link first node with the second node
head->next = second;
/* data has been assigned to data part of first
block (block pointed by head). And next
pointer of first block points to second.
So they both are linked.
head second third
| | |
| | |
+---+---+ +----+----+ +-----+----+
| 1 | o----->| # | # | | # | # |
+---+---+ +----+----+ +-----+----+
*/
// assign data to second node
second->data = 2;
// Link second node with the third node
second->next = third;
/* data has been assigned to data part of second
block (block pointed by second). And next
pointer of the second block points to third
block. So all three blocks are linked.
head second third
| | |
| | |
+---+---+ +---+---+ +----+----+
| 1 | o----->| 2 | o-----> | # | # |
+---+---+ +---+---+ +----+----+ */
third->data = 3; //assign data to third node
third->next = NULL;
/* data has been assigned to data part of third
block (block pointed by third). And next pointer
of the third block is made NULL to indicate
that the linked list is terminated here.
We have the linked list ready.
head
|
|
+---+---+ +---+---+ +----+------+
| 1 | o----->| 2 | o-----> | 3 | NULL |
+---+---+ +---+---+ +----+------+
Note that only head is sufficient to represent
the whole list. We can traverse the complete
list by following next pointers. */
return 0;
}
// A simple Java program to introduce a linked list
class LinkedList
{
Node head; // head of list
/* Linked list Node. This inner class is made static so that
main() can access it */
static class Node {
int data;
Node next;
Node(int d) { data = d; next=null; } // Constructor
}
/* method to create a simple linked list with 3 nodes*/
public static void main(String[] args)
{
/* Start with the empty list. */
LinkedList llist = new LinkedList();
llist.head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
/* Three nodes have been allocated dynamically.
We have refernces to these three blocks as first,
second and third
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | null | | 2 | null | | 3 | null |
+----+------+ +----+------+ +----+------+ */
llist.head.next = second; // Link first node with the second node
/* Now next of first Node refers to second. So they
both are linked.
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | o-------->| 2 | null | | 3 | null |
+----+------+ +----+------+ +----+------+ */
second.next = third; // Link second node with the third node
/* Now next of second Node refers to third. So all three
nodes are linked.
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | o-------->| 2 | o-------->| 3 | null |
+----+------+ +----+------+ +----+------+ */
}
}
// A simple C/C++ program to introduce
// a linked list
#include<bits/stdc++.h>
using namespace std;
// Linked List Node
struct Node
{
int data; // Data
struct Node *next; // Pointer
};
// This function prints contents of linked list
// starting from the given node
void printList(Node *node)
{
while (node != NULL)
{
cout<<node->data<<" ";
node = node->next;
}
}
// Program to create a simple linked
// list with 3 nodes
int main()
{
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;
// allocate 3 nodes in the heap
head = new Node;
second = new Node;
third = new Node;
/* Three blocks have been allocated dynamically.
We have pointers to these three blocks as first,
second and third
head second third
| | |
| | |
+---+-----+ +----+----+ +----+----+
| # | # | | # | # | | # | # |
+---+-----+ +----+----+ +----+----+
# represents any random value.
Data is random because we haven’t assigned
anything yet */
head->data = 1; //assign data in first node
// Link first node with the second node
head->next = second;
/* data has been assigned to data part of first
block (block pointed by head). And next
pointer of first block points to second.
So they both are linked.
head second third
| | |
| | |
+---+---+ +----+----+ +-----+----+
| 1 | o----->| # | # | | # | # |
+---+---+ +----+----+ +-----+----+
*/
// assign data to second node
second->data = 2;
// Link second node with the third node
second->next = third;
/* data has been assigned to data part of second
block (block pointed by second). And next
pointer of the second block points to third
block. So all three blocks are linked.
head second third
| | |
| | |
+---+---+ +---+---+ +----+----+
| 1 | o----->| 2 | o-----> | # | # |
+---+---+ +---+---+ +----+----+ */
third->data = 3; //assign data to third node
third->next = NULL;
/* data has been assigned to data part of third
block (block pointed by third). And next pointer
of the third block is made NULL to indicate
that the linked list is terminated here.
We have the linked list ready.
head
|
|
+---+---+ +---+---+ +----+------+
| 1 | o----->| 2 | o-----> | 3 | NULL |
+---+---+ +---+---+ +----+------+
Note that only head is sufficient to represent
the whole list. We can traverse the complete
list by following next pointers. */
// Print the linked list
printList(head);
return 0;
}
// A simple Java program for traversal
// of a linked list
class LinkedList
{
Node head; // head of list
/* Linked list Node. This inner class is made static so that
main() can access it */
static class Node {
int data;
Node next;
Node(int d) { data = d; next=null; } // Constructor
}
/* This function prints contents of linked
list starting from head */
public void printList()
{
Node n = head;
while (n != null)
{
System.out.print(n.data+" ");
n = n.next;
}
}
/* method to create a simple linked list with 3 nodes*/
public static void main(String[] args)
{
/* Start with the empty list. */
LinkedList llist = new LinkedList();
llist.head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
llist.head.next = second; // Link first node with the second node
second.next = third; // Link first node with the second node
llist.printList();
}
}
Output: 1 2 3
Given the head node of a linked list, the task is to insert a new node in this already created linked list.



Given the head pointer pointing to the Head of a singly linked list and a node to be deleted from the list. Delete the given node from the Linked List.

// Find next node using next pointer
struct Node *temp = node_ptr->next;
// Copy data of next node to this node
node_ptr->data = temp->data;
// Unlink next node
node_ptr->next = temp->next;
// Delete next node
free(temp);

Creating and Traversing a Doubly Linked List
Creating and Traversing a doubly linked list is almost similar to that of the singly linked lists. The only difference is that in doubly linked lists we need to maintain an extra previous pointer for every node while creating the list.
// A complete working C++ program to demonstrate
// Doubly Linked Lists
#include <bits/stdc++.h>
using namespace std;
// A linked list node
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// This function prints contents of Doubly linked
// list starting from the given node
void printList(struct Node* node)
{
struct Node* last;
// Traverse the linked list in forward direction
// using the next node's pointer present
// at each node
cout<<"\nTraversal in forward direction \n";
while (node != NULL) {
cout<<node->data<<" ";
last = node;
node = node->next;
}
// Traverse the linked list in reverse direction
// starting from the last node using the previous
// node's pointer present at each node
printf("\nTraversal in reverse direction \n");
while (last != NULL) {
cout<<last->data<<" ";
last = last->prev;
}
}
/* Given a reference (pointer to pointer) to the head
of a DLL and an int, this function inserts
a new node at the end */
void append(struct Node** head_ref, int new_data)
{
/* 1. allocate node */
Node* new_node = new Node;
struct Node* last = *head_ref; /* used in step 5*/
/* 2. put in the data */
new_node->data = new_data;
/* 3. This new node is going to be the last node, so
make next of it as NULL*/
new_node->next = NULL;
/* 4. If the Linked List is empty, then make the new
node as head */
if (*head_ref == NULL) {
new_node->prev = NULL;
*head_ref = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last->next != NULL)
last = last->next;
/* 6. Change the next of last node */
last->next = new_node;
/* 7. Make last node as previous of new node */
new_node->prev = last;
return;
}
/* Driver program to test above functions*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
// Insert 6. So linked list becomes 6->NULL
append(&head, 6);
// Insert 7 at the end.
// So linked list becomes 6->7->NULL
append(&head, 7);
// Insert 1 at the end.
// So linked list becomes 6->7->1->NULL
append(&head, 1);
// Insert 4 at the end.
// So linked list becomes 6->7->1->4->NULL
append(&head, 4);
cout<<"Created DLL is: ";
printList(head);
return 0;
}
// A complete working Java program to demonstrate
// Doubly Linked List
public class DLL {
Node head; // head of list
/* Doubly Linked list Node*/
class Node {
int data;
Node prev;
Node next;
// Constructor to create a new node
// next and prev is by default initialized as null
Node(int d) { data = d; }
}
// Add a node at the end of the list
void append(int new_data)
{
/* 1. allocate node
2. put in the data */
Node new_node = new Node(new_data);
Node last = head; /* used in step 5 */
/* 3. This new node is going to be the last node, so
make next of it as NULL */
new_node.next = null;
/* 4. If the Linked List is empty, then make the new
node as head */
if (head == null) {
new_node.prev = null;
head = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last.next != null)
last = last.next;
/* 6. Change the next of last node */
last.next = new_node;
/* 7. Make last node as previous of new node */
new_node.prev = last;
}
// This function prints contents of linked list
// starting from the given node
public void printlist(Node node)
{
Node last = null;
// Traverse the linked list in forward direction
// using the next node's pointer present
// at each node
System.out.println("Traversal in forward Direction");
while (node != null) {
System.out.print(node.data + " ");
last = node;
node = node.next;
}
System.out.println();
// Traverse the linked list in reverse direction
// starting from the last node using the previous
// node's pointer present at each node
System.out.println("Traversal in reverse direction");
while (last != null) {
System.out.print(last.data + " ");
last = last.prev;
}
}
/* Driver program to test above functions*/
public static void main(String[] args)
{
/* Start with the empty list */
DLL dll = new DLL();
// Insert 6. So linked list becomes 6->NULL
dll.append(6);
// Insert 7. So linked list becomes 6->7->NULL
dll.append(7);
// Insert 1. So linked list becomes 6->7->1->NULL
dll.append(1);
// Insert 4. So linked list becomes 6->7->1->4->NULL
dll.append(4);
System.out.println("Created DLL is: ");
dll.printlist(dll.head);
}
}
Created DLL is:
Traversal in forward direction
6 7 1 4
Traversal in reverse direction
4 1 7 6

A circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.


Why have we taken a pointer that points to the last node instead of first node?
For insertion of node in the beginning we need to traverse the whole list. Also, for insertion at the end, the whole list has to be traversed. If instead of start pointer we take a pointer to the last node then in both the cases there won’t be any need to traverse the whole list. So, insertion in the begging or at the end takes constant time irrespective of the length of the list.
// A complete C++ program to demonstrate the
// working of Circular Linked Lists
#include<bits/stdc++.h>
using namespace std;
// Circular Linked List Node
struct Node
{
int data;
struct Node *next;
};
// Function to add a node at the end of a
// Circular Linked List
struct Node *addEnd(struct Node *last, int data)
{
if (last == NULL)
{
// Creating a node dynamically.
struct Node *temp = new Node;
// Assigning the data.
temp -> data = data;
last = temp;
// Creating the link.
last -> next = last;
return last;
}
struct Node *temp = new Node;
temp -> data = data;
temp -> next = last -> next;
last -> next = temp;
last = temp;
return last;
}
// Function to traverse a Circular Linked list
// Using a pointer to the Last Node
void traverse(struct Node *last)
{
struct Node *p;
// If list is empty, return.
if (last == NULL)
{
cout << "List is empty." << endl;
return;
}
// Pointing to first Node of the list.
p = last -> next;
// Traversing the list.
do
{
cout << p -> data << " ";
p = p -> next;
}
while(p != last->next);
}
// Driver Program
int main()
{
struct Node *last = NULL;
last = addEnd(last, 6);
last = addEnd(last, 4);
last = addEnd(last, 2);
last = addEnd(last, 8);
last = addEnd(last, 12);
last = addEnd(last, 10);
traverse(last);
return 0;
}
// A complete Java program to demonstrate the
// working of Circular Linked Lists
class CLL
{
// A circular linked list node
static class Node
{
int data;
Node next;
};
// Function to insert a node in a Circular
// linked list at the end
static Node addEnd(Node last, int data)
{
if (last == null)
{
// Creating a node dynamically.
Node temp = new Node();
// Assigning the data.
temp.data = data;
last = temp;
// Creating the link.
last.next = last;
return last;
}
Node temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
// Function to traverse a given Circular Linked
// List using the Last pointer
static void traverse(Node last)
{
Node p;
// If list is empty, return.
if (last == null)
{
System.out.println("List is empty.");
return;
}
// Pointing to first Node of the list.
p = last.next;
// Traversing the list.
do
{
System.out.print(p.data + " ");
p = p.next;
}
while(p != last.next);
}
// Driver code
public static void main(String[] args)
{
Node last = null;
last = addEnd(last, 6);
last = addEnd(last, 4);
last = addEnd(last, 2);
last = addEnd(last, 8);
last = addEnd(last, 12);
last = addEnd(last, 10);
traverse(last);
}
}
Output: 6 4 2 8 12 10
Input: Head of following linked listThree Pointers Solution : We will be using three auxiliary three pointers prev, current and next to reverse the links of the linked list. The solution can be understood by the below animation, how links are reversed.
1->2->3->4->NULL
Output: Linked list should be changed to,
4->3->2->1->NULL

void reverse(Node* head)
{
// Initialize current, previous and
// next pointers
Node *current = head;
Node *prev = NULL, *next = NULL
while (current != NULL)
{
// Store next
next = current->next
// Reverse current node's pointer
current->next = prev
// Move pointers one position ahead.
prev = current
current = next
}
head = prev
}
void reverse(Node* head)
{
// Initialize current, previous and
// next pointers
Node *current = head;
Node *prev = NULL, *next = NULL
while (current != NULL)
{
// Store next
next = current->next
// Reverse current node's pointer
current->next = prev
// Move pointers one position ahead.
prev = current
current = next
}
head = prev
}
Node* reverse(Node* node)
{
if (node == NULL) :
return NULL
if (node->next == NULL) :
head = node
return node
Node* temp = reverse(node->next)
temp->next = node
node->next = NULL
return node
}
Hashing Solution :Traverse the list one by one and keep putting the node addresses in a Hash Table. At any point, if NULL is reached then return false and if next of current node points to any of the previously stored nodes in Hash then return true.bool detectLoop(Node* h)
{
seen //HashMap
while (h != NULL)
{
// If this node is already present
// in hashmap it means there is a cycle
// (Because you we encountering the
// node for the second time).
if (seen.find(h) == True)
return true
// If we are seeing the node for
// the first time, insert it in hash
seen.insert(h)
h = h->next
}
return false
}
bool detectloop(Node* head)
{
Node *slow_p = head, *fast_p = head
while (slow_p && fast_p && fast_p->next)
{
slow_p = slow_p->next
fast_p = fast_p->next->next
if (slow_p == fast_p)
return true
}
return false
}

/* function to get the intersection point of two linked
lists head1 and head2 */
int getIntesectionNode( Node* head1, Node* head2)
{
c1 = getCount(head1)
c2 = getCount(head2)
d // difference
if(c1 > c2)
d = c1 - c2
return utility(d, head1, head2)
else :
d = c2 - c1
return utility(d, head2, head1)
}
/* function to get the intersection point of two linked
lists head1 and head2 where head1 has d more nodes than
head2 */
int utility(d, Node* head1, Node* head2)
{
Node* current1 = head1
Node* current2 = head2
for ( i = 0 to d-1 )
{
if(current1 == NULL)
return -1
current1 = current1->next
}
while(current1 != NULL && current2 != NULL)
{
if(current1 == current2)
return current1->data
current1= current1->next
current2= current2->next
}
return -1
}
A | Insertion Sort |
B | Quick Sort |
C | Heap Sort |
D | Merge Sort |